/*
 * @lc app=leetcode.cn id=1601 lang=cpp
 *
 * [1601] 最多可达成的换楼请求数目
 */

// @lc code=start
class Solution
{
public:
    int getRequests(int num)
    {
        int ret = 0;
        while (num != 0)
        {
            ret++;
            num &= num - 1;
        }
        return ret;
    }
    int checkRequest(int mask, int n, vector<vector<int>> &requests, vector<int> delta)
    {
        int m = requests.size();
        fill(delta.begin(), delta.end(), 0);
        for (int i = 0; i < m; i++)
        {
            if ((mask & (1 << i)) == 0)
            {
                continue;
            }
            int a = requests[i][0];
            int b = requests[i][1];
            delta[a]++;
            delta[b]--;
        }
        for (auto x : delta)
        {
            if (x != 0)
            {
                return 0;
            }
        }
        return 1;
    }
    int maximumRequests(int n, vector<vector<int>> &requests)
    {
        int m = requests.size();
        int ans = 0;
        vector<int> delta(n);
        for (int mask = 1; mask < (1 << m); mask++)
        {
            int cnt = getRequests(mask);
            if (cnt <= ans)
            {
                continue;
            }
            if (checkRequest(mask, n, requests, delta))
            {
                ans = cnt;
            }
        }
        return ans;
    }
};
// @lc code=end
